Math 512: Finite Model Theory RPC and r.e.

February 3, 1997

We work in a finite relational language. For simplicity, we assume the language has one ternary relation symbol: R. Following Vaanenen, a finite stucture A is coded as a sequence c(A): m#p. m is binary for the number of elements in A. We assume A is in ‘standard position”. That is the universe of A is an integer n. p is a sequence of length n^{3} of 0’s and 1’s depending on whether the ith element in a lexiocographic ordering of A^{3} (depending on the underlying order of A is or is not in R.

0.1 Definition. A class K of finite L-structures is relativized pseudo-elementary if there is a language L^{+} extending L with a new predicate P and an L^{+}-sentence θ such that for every finite L^{+}-structure B,

B ⊧ θ iff P (B)|L ∈ K.

0.2 Theorem. Let K be a collection of finite L-structures closed under isomorphism. Then then the set {c(A) : A ∈ K} is recursively enumerable if and only if K is the collection of finite models of a relatively psuedo-elementary class.

Proof. If K is rpc, we can recursively enumerate K just by examining the finite models of θ.

For the converse, let M be the Turing machine which accepts (codes of ) members of K. Fix the language L^{+} to have two unary predicates P and Q, a binary relation <, a unary predicate T, the language of L, binary predicates B_{0}(x, t),B_{1}(x, t),B_{#}(x, t), S(x, y) and C_{q}(x, t), which encode the action M,

We provide below the key points of the coding. Various boundary conditions are implicit. Also, to clarify specifying that Q contains the code for (P (A), different notations for 0’s and 1’s preceding or following are used. Of course, M only sees one kind of 0 or 1.

Let θ assert: i) P and Q partition the universe. ii) The symbols of L apply only to elements of P. iii) < is a linear order (separately) of each of P and Q, T is the terminal element of P. iv) B_{0}(x, t),B_{1}(x, t), S(x, y) and C_{q}(x, t), encode the action M on input c(A) which

halts just if c(A) is the code of an element of K.

v) sentences asserting that the initial segment of Q is binary for the length of A. For Q(x) and P (t);

(a) B′_{0}(0, t), C′_{0}(x, t).

(b) t < T ∧ B′_{0}(x + 1, t) ∧ C′_{0}(x, t + 1) → B′_{0}(x + 1, t + 1) ∧ C′_{0}(x + 1, t + 1)

(c) t < T ∧ B′_{0}(x + 1, t) ∧ C′_{1}(x, t + 1) → B′_{1}(x + 1, t + 1) ∧ C′_{0}(x + 1, t + 1)

(d) t < T ∧ B′_{1}(x + 1, t) ∧ C′_{0}(x, t + 1) → B′_{1}(x + 1, t + 1) ∧ C′_{0}(x + 1, t + 1)

(e) t < T ∧ B′_{1}(x + 1, t) ∧ C′_{1}(x, t + 1) → B′_{0}(x + 1, t + 1) ∧ C′_{1}(x + 1, t + 1)

(f) t = T → C′_{h}(x, T) ∧ B_{#}(x + 1, t), vi) for P (x_{i}) and Q(f(x_{1}, x_{2}, x_{3})):

(a) B_{#}(x, T) → S(x, f(0, 0, 0);

1. S(f(x_{1}, x_{2}, x_{3}), f(x_{1}, x_{2}, S(x_{3})) if x_{3} < T
2. S(f(x_{1}, x_{2}, x_{3}), f(x_{1}, S(x_{2}), 0) if x_{3} = T, etc.

(b) B_{1}(f(x_{0}, x_{1}, x_{2}) iff R(x_{0}, x_{1}, x_{2}).

(c) Q(x) → x < # ∨ (∃\overline{x})x = f(\overline{x}). Now, B ⊧ θ and B finite implies that Q(B) is a computation of M accepting

c(P (B)|L), so P (B)|L) ∈ K as required. And clearly each member of K can be expanded to a finite model of θ.

Note that much of the effort was to code the cardinality of P (A) in binary. This is totally irrelevant to the theorem at hand; we could use the 1-ary representation. It could be important for finer complexity computations.